package sort;

/**
 * @author RunningShrimp
 * @date 2021/6/9  16:29
 * @see <a href=""></a>
 */
public class QuickSort<E extends Comparable<E>> extends BaseSort<E> {
    @Override
    protected void sort(E[] array) {
        sort(array, 0, array.length - 1);
    }

    private void sort(E[] array, int l, int r) {
        if (l >= r) {
            return;
        }
        int p = partition(array, l, r);
        sort(array, l, p - 1);
        sort(array, p + 1, r);
    }

    private int partition(E[] array, int l, int r) {
        E v = array[l];

        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (less(v, array[i])) {
                j++;
                exchange(array, j, i);
            }
        }
        exchange(array, j, l);
        return j;

    }

    public static void main(String[] args) {
        Integer[] array = BaseSort.generateArray(10, 100);
        BaseSort<Integer> sort = new QuickSort<>();
        System.out.println("排序前：");
        sort.show(array);
        sort.sort(array);
        System.out.println("排序后");
        sort.show(array);
        System.out.println("是否有序：" + sort.isSorted(array));
    }
}
